//给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
//
// 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
//
//
//
// 示例 1：
//
//
//输入：s = "bbbab"
//输出：4
//解释：一个可能的最长回文子序列为 "bbbb" 。
//
//
// 示例 2：
//
//
//输入：s = "cbbd"
//输出：2
//解释：一个可能的最长回文子序列为 "bb" 。
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 1000
// s 仅由小写英文字母组成
//
// Related Topics 字符串 动态规划 👍 823 👎 0

package leetcode.editor.cn;
class 最长回文子序列{
    public static void main(String[] args) {
        Solution solution = new 最长回文子序列().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestPalindromeSubseq(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        //出一个dp
        int[][] dp = new int[N][N];
        dp[N - 1][N - 1] = 1;//右下角先填上
        //对角线和 紧挨着对角线的一条
        for (int i = 0; i < N - 1; i++) {
            dp[i][i] = 1;
            dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
        }
        //从下往上 从左往右
        for (int L = N - 3; L >= 0; L--) {
            for (int R = L + 2; R < N; R++) {
                dp[L][R] = Math.max(dp[L][R - 1], dp[L + 1][R]);
                if (str[L] == str[R]) {
                    dp[L][R] = Math.max(dp[L][R], 2 + dp[L + 1][R - 1]);
                }
                //几种可能性优化
                //int p1 = dp[L + 1][R];
                //int p2 = dp[L][R - 1];
                //int p3 = dp[L + 1][R - 1];
                //int p4 = str[L] == str[R] ? 2 + dp[L + 1][R - 1] : 0;
                //dp[L][R] = Math.max(Math.max(p1, p2), Math.max(p3, p4));

                //减小看左下的次数
                dp[L][R] = Math.max(dp[L][R - 1], dp[L + 1][R]);
                if (str[L] == str[R]) {
                    dp[L][R] = Math.max(dp[L][R], 2 + dp[L + 1][R - 1]);
                }
            }
        }
        return dp[0][N-1];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
